题目描述

给定一个数组 $A[0,1,…,n-1]$，请构建一个数组 $B[0,1,…,n-1]$，其中 $B[i]$ 的值是数组 $A$ 中除了下标 $i$ 以外的元素的积, 即 $B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]$。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示：

• 所有元素乘积之和不会溢出 32 位整数
• $a.length <= 100000$

---

算法

(前后缀分解,模拟) $O(n)$

对于每一个数的结果都可以分成两部分的乘积，左边所有数的乘积 * 右边所有数的乘积

1. 从前往后遍历数组，使用一个临时变量 $p$ 记录当前位置前的所有数的乘积，同时记录此时的结果 $res[i]$
2. 从后往前遍历数组，使用一个临时变量 $p$ 记录当前位置后的所有数的乘积，将 $p * res[i]$ 就是当前位置左右两部分乘积的结果。

时间复杂度

$O(n)$

空间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> res(a.size());
        for (int i = 0, p = 1; i < a.size(); i ++ ) {
            res[i] = p;
            p *= a[i];
        }
        
        for (int i = a.size() - 1, p = 1; i >= 0; i -- ) {
            res[i] *= p;
            p *= a[i];
        }

        return res;
    }
};